package com.fmm.hard;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

public class TwentyFourPoint {
    public static boolean judgePoint24(int[] cards) {
        Fraction[] cs = new Fraction[cards.length];
        for (int i = 0; i < cards.length; i++) {
            cs[i] = new Fraction(cards[i], 1, String.valueOf(cards[i]));
        }
        return judgePoint24(cs);
    }

    private static boolean judgePoint24(Fraction[] cards) {
        if (cards.length == 1) {
            Fraction result = cards[0];
            if (result.equals24()) {
                System.out.println(result.expression);
                return true;
            }
            return false;
        }

        Set<Fraction[]> combinations = new HashSet<>();
        for (int i = 0; i < cards.length - 1; i++) {
            for (int j = i + 1; j < cards.length; j++) {
                Fraction card1 = cards[i];
                Fraction card2 = cards[j];
                int[] remainIndex = calculateRemainIndex(i, j, cards.length);
                Fraction r;
                for (int k = 0; k < 6; k++) {
                    if (k == 0) {
                        r = Fraction.add(card1, card2);
                    } else if (k == 1) {
                        r = Fraction.subtract(card1, card2);
                    } else if (k == 2) {
                        r = Fraction.subtract(card2, card1);
                    } else if (k == 3) {
                        r = Fraction.multiply(card1, card2);
                    } else if (k == 4) {
                        if (card2.numerator == 0) {
                            continue;
                        }
                        r = Fraction.divide(card1, card2);
                    } else {
                        if (card1.numerator == 0) {
                            continue;
                        }
                        r = Fraction.divide(card2, card1);
                    }
                    Fraction[] subCards = new Fraction[remainIndex.length + 1];
                    for (int m = 0; m < subCards.length; m++) {
                        if (m == subCards.length - 1) {
                            subCards[m] = r;
                        } else {
                            subCards[m] = cards[remainIndex[m]];
                        }
                    }
                    combinations.add(subCards);
                }
            }
        }
        return combinations.stream().anyMatch(subCards -> judgePoint24(subCards));
    }

    private static int[] calculateRemainIndex(int i, int j, int size) {
        if (size <= 2) {
            return new int[]{};
        }
        int[] result = new int[size - 2];
        int rIndex = 0;
        for (int k = 0; k < size; k++) {
            if (k != i && k != j) {
                result[rIndex++] = k;
            }
        }
        return result;
    }

    private static class Fraction {
        private final Integer numerator;
        private final Integer denominator;
        private final String expression;

        public Fraction(Integer numerator, Integer denominator, String expression) {
            // 最大公约数
            BigInteger gcd = BigInteger.valueOf(numerator).gcd(BigInteger.valueOf(denominator));
            this.numerator = BigInteger.valueOf(numerator).divide(gcd).intValue();
            this.denominator = BigInteger.valueOf(denominator).divide(gcd).intValue();
            this.expression = expression;
        }

        public static Fraction add(Fraction a, Fraction b) {
            return new Fraction(a.numerator * b.denominator + a.denominator * b.numerator, a.denominator * b.denominator,
                    "(" + a.expression + " + " + b.expression + ")");
        }

        public static Fraction subtract(Fraction a, Fraction b) {
            return new Fraction(a.numerator * b.denominator - a.denominator * b.numerator, a.denominator * b.denominator,
                    "(" + a.expression + " - " + b.expression + ")");
        }

        public static Fraction multiply(Fraction a, Fraction b) {
            return new Fraction(a.numerator * b.numerator, a.denominator * b.denominator,
                    "(" + a.expression + " * " + b.expression + ")");
        }

        public static Fraction divide(Fraction a, Fraction b) {
            return new Fraction(a.numerator * b.denominator, a.denominator * b.numerator,
                    "(" + a.expression + " / " + b.expression + ")");
        }

        public boolean equals24() {
            return this.numerator == 24 && this.denominator == 1;
        }
    }

    public static void main(String[] args) {
        System.out.println(judgePoint24(new int[]{3, 3, 8, 8}));
    }
}
